class ListNode{
    constructor(value,next) {
        this.value = value;
        this.next = next;
    }
}

class TreeNode{
    constructor(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}

/**
 * 最长子序列
 * 解题思路 滑动窗口机制
 *
 * @param s
 * @returns {number}
 */
const lengthOfLongestSubstring = (s) => {
    if(s.length === 0) return 0;
    let maxLen = 0;
    let length = 0;
    let map = new Map();
    for(let i = 0; i < s.length; i++){
        let char = s[i];
        if(!map.has(char)){
            map.set(char, i);
            ++length;
            if(length > maxLen){
                maxLen = length;
            }
        }else{
            let front = map.get(s[i]);
            map.set(s[i], i);
            length = (i - front);
        }
    }
    return maxLen;
};

/**
 * 两个数组中位数  先合并两个数组，再求中位数
 * 下面的实现太完美 可以考虑简化
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const findMedianSortedArrays = function(nums1, nums2) {
    let mergeArr = [];
    let len1 = nums1.length, len2 = nums2.length;
    let totalLen = len1 + len2;
    if(len1 && len2){
        while (len1 && len2){
            let num1 = nums1[0];
            let num2 = nums2[0];
            if(num1 < num2){
                mergeArr.push(num1);
                nums1.shift();
                len1--;
            }else{
                mergeArr.push(num2);
                nums2.shift();
                len2--;
            }
        }
        while (len1){
            mergeArr.push(nums1.shift());
            len1--;
        }
        while (len2){
            mergeArr.push(nums2.shift());
            len2--;
        }
    }else{
        if(nums1.length === 0) mergeArr = nums2;
        if(nums2.length === 0) mergeArr = nums1;
    }

    let mid = totalLen / 2;
    let rest = totalLen % 2;
    if(mid === 0) return 0;
    if(mid < 1) return mergeArr[0];
    if(rest === 0){
        return (mergeArr[mid] + mergeArr[mid-1]) / 2;
    }else{
        return mergeArr[Math.floor(mid)];
    }
};

/**
 * 文斌大大龙 算法 【35】 篇
 * LeetCode 第 496 题
 *
 * 下一个更大元素
 *
 * 两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是nums2 的子集。
 * 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
 *
 * 解题思路 单调栈  解决 NEG 的问题
 *
 * @param Number[] nums1
 * @param Number[] nums2
 */
const nextGraterElement = function(nums1, nums2){
    let setMap = (nums) => {
        // 这个map初始化映射都是 -1
        let [map, stack] = [new Map(nums2.map(item => [item, -1])), []];
        for (let i = 0; i < nums.length; i++) {
            while (stack.length !== 0 && nums[i] > stack[stack.length - 1]){
                map.set(stack.pop(), nums[i]);
            }
            stack.push(nums[i]);
        }
        return map;
    }
    let numsMap = setMap(nums2);
    return nums1.map(item => numsMap.get(item));
};

/**
 * 文斌大大龙 第 【35】 篇
 *  LeetCode 第 503 题
 *
 *  下一个更大元素 2
 *
 *  给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），
 *  输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，
 *  这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。
 *  如果不存在，则输出 -1。
 *
 *  解法思路 单调栈
 *
 *  这个题跟上一个题目的变化是 循环， 使用取模运算 % 可以吧下标 映射到数组 nums 长度的 0-N 内。
 *  注意 stack中放置的是 下标。
 *  接下来跟上面一模一样的单调栈方法解决问题
 *
 *  @params Number[] nums
 *
 */

const nextGraterElement2 = function (nums) {
    let [len, stack, result] = [nums.length, [], new Array(nums.length).fill(-1)];
    // 首先把 nums 假设扩展成 2 倍长度， stack 中存放的是下标
    for (let i = 0; i < len * 2 - 1; i++) {
        while (stack.length !== 0 && nums[i % len] > nums[stack[stack.length - 1]]) {
            result[stack.pop()] = nums[i % len];
        }
        stack.push(i % len);
    }
    return result;
}

/**
 * 文斌大大龙算法 【36】 期
 * LeetCode 第 739 题
 *
 * 给定一个整数数组 temperatures，
 * 表示每天的温度，返回一个数组 answer，
 * 其中answer[i]是指在第 i 天之后，才会有更高的温度。
 * 如果气温在这之后都不会升高，请在该位置用 0 来代替。
 *
 * 解题思路 单调栈 方式 具体步骤
 *
 * 1. 正向遍历温度列表。
 *
 *
 * 2. 对于温度列表中的每个元素 T[i]，
 *    （1）如果栈为空，则直接将 i 进栈，
 *    （2）如果栈不为空，则比较栈顶元素 prevIndex 对应的温度 T[prevIndex] 和当前温度 T[i]，
 *    （3）如果 T[i] > T[prevIndex]，则将 prevIndex 移除，并将 prevIndex 对应的等待天数赋为 i - prevIndex，
 *    重复上述操作直到栈为空或者栈顶元素对应的温度小于等于当前温度，然后将 i 进栈。
 *
 */

const dailyTemperatures = function(T){
    let [stack, res] = [[], new Array(T.length).fill(0)];
    for (let i = 0; i < T.length; i++) {
        if(stack.length !== 0 && T[i] > T[stack[stack.length - 1]]){
            let prevIndex = stack[stack.length - 1];
            stack.pop();
            res[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return res;
}

/**
 * 文斌大大龙 算法 【36】 期
 * LeetCode 第 84 题
 * 柱状图中的最大的矩形
 *
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 *
 * 解题思路 单调栈
 *
 * 基本步骤
 *
 * 维护一个 stack 栈。遍历 heights 数组的每一个 bar
 * 当前 bar 比栈顶的 bar 高，直接入栈
 * 当前 bar 比栈顶的 bar 矮：
 *      栈顶元素（索引）出栈，暂存给 stackTopIndex 变量
 *      计算以 heights[stackTopIndex] 为高的长方形的面积，宽度 = 当前 bar 的索引 i - 新的栈顶索引 - 1 ，与全局的最大比较
 *      当前 bar 继续和新的栈顶比较，重复上面过程，直到当前 bar 不再比栈顶的 bar 矮，入栈
 *
 */

const largestRectangleArea = function(heights){
    if(!heights || !heights.length){
        return 0;
    }
    // 两边添加虚拟bar 0, 巧妙处理下面遍历 while 的终止条件
    heights.unshift(0);
    heights.push(0);
    // 获取栈顶元素的纯函数
    const stackTopItem = () => stack[stack.length - 1];
    let [maxArea, stack] = [0, []];
    for (let i = 0; i < heights.length; i++) {
        while (stack.length && heights[stackTopItem()] > heights[i]){
            // 栈顶元素出栈，并保存栈顶 bar 的索引
            const stackTopIndex = stack.pop();
            // 得到与左侧最近项最大宽度
            const width = i - stackTopItem() - 1;
            // 计算面积
            maxArea = Math.max(maxArea, width * heights[stackTopIndex]);
        }
        // 当前bar比栈顶高了，入栈
        stack.push(i);
    }
    return maxArea;
};

/**
 * 文斌大大龙 第 【37】 期
 * LeetCode 第 86 题
 *
 * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
 * 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 *
 * 基本思路
 * 1. 新构造 2 个链表， 一个链表专门存储比 X 小的节点，另一个专门存储比 X 大的节点
 * 2. 再原链表头部开始扫描一遍，依次把这两类点归类到2个新建的链表之中
 * 3. 由于是从头开始扫描的原链表，所以原链表的顺序会依旧被保存下来。
 * 4. 最后2个新链表里面会存储好各自的结果，把这两个链表，比 x 小的链表拼接到比 x 大的链表前面
 * 就是最后的答案了。
 */

const partition = function(head, x){
    // 建立两个链表，分别为大于 X 和 小于 X 的链表
    let [small, big] = [new ListNode(0), new ListNode(0)];
    // 建立两个链表的虚拟头节点，处理头节点为空的边界条件更加方便;
    let [smallHead, bigHead] = [small, big];
    // 开始分区，形成small 和 big 链表
    while(head !== null){
        if(head.value < x){
            small.next = head;
            small = small.next;
        }else{
            big.next = head;
            big = big.next;
        }
        head = head.next;
    }
    // big 数组尾部置空
    big.next = null;
    // 数组链接
    small.next = bigHead.next;
    return smallHead.next;
}

/**
 * 文斌大大龙算法第 【39】 篇
 * leetcode 第 92 题目
 * 反转链表
 *
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 */

const reverseBetween = function(head,left,right){
    let preHead = new ListNode(0);
    preHead.next = head;
    let pre = preHead;
    // pre 永远指向带反转区域的前一个节点
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next;
    }
    // cur 指向当前待反转区域的第一个节点
    let cur = pre.next;
    for (let i = 0; i < right - left; i++) {
        // next 永远指向 cur 的下一个节点，循环过程中， cur变化后 next 会变化
        let next = cur.next;
        cur.next = next.next;
        next.next = pre.next;
        pre.next = next;
    }
    return preHead.next;
}

/**
 * 文斌大大龙算法第【39】
 * leetCode 第 93 题
 * 复原 IP 地址
 *
 * 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 算法 解题思路 DFS + 回溯
 *
 * 其实也可以使用正则表达式来提取 IP 字符串 这样效果简单
 *
 */

// 不过这里我们还是先用代码的方式来解决，首先回顾一下 DFS 的模板状态

/*const dfsProblems = function(s){
    let res = []; //结果集
    let dfs = (curPath, start(可选参数)) => {
        if(符合条件){
            res.push(xFunctions(curPath));
        }
        if(剪枝条件) return;
        // 下面是根据题意，有几个岔路，开始选择
        for(){
            curPath.push(xxx);
            dfs(curPath, start(可选参数)) // 深度递归
            // 回溯
            curPath.pop()
        }
    }
    dfs([], start(可选参数));
    return res;
}*/

// 本题目是通过字符串截取的方式，一共有三种可选择路径
const restoreIPAddress = function(s){
    let [res, len] = [[], s.length];
    let dfs = (curPath, segStart) =>{
        // 如果1, 找到了4段合法片段，并且2，遍历完了所有字符串，那么就是一种答案
        if(curPath.length === 4){
            if(segStart === len){
                res.push(curPath.join("."));
            }else{
                // 还没遍历完 剪枝
                return;
            }
        }
        // 每个 curPath 中的元素长度可能是 1，2，3 遍历
        for (let segLen = 1; segLen <= 3 ; segLen++) {
            // 直接超出长度
            if(segStart + segLen > len){
                return;
            }
            // 除非只有一位 0， 不能有先导 0
            if(segLen !== 1 && s[segStart] === '0'){
                return;
            }
            // 当前被切出的片段
            let segStr = s.substring(segStart, segStart + segLen);
            if(segLen === 3 && segStr * 1 > 255){
                // 不能超过255
                return;
            }
            // 回溯基本操作
            curPath.push(segStr);
            dfs(curPath,segStart + segLen);
            curPath.pop();
        }
    }
    dfs([],0);
    return res;
};

/**
 * 文斌大大龙算法 【40】 篇
 * LeetCode 中序遍历
 * 二叉树的遍历
 */

const midOrderTraversal = function (root){
    let res = [];
    let stack = [];
    let p = root;
    while (stack.length || p){
        if(p){
            stack.push(p);
            p = p.left;
        }
        let node = stack.pop();
        res.push(node.value);
        p = node.right;
    }
};

/**
 * 文斌大大龙 第 【40】 篇
 * LeetCode 第 95 题
 * 不同的二叉搜索树 BSF
 * 给定一个整数 n，生成所有由 1 ... n 为节点所组成的 二叉搜索树 。
 *
 * 解题思路 DFS + 分治法
 */

const generateTrees = function(n){
    const dfs = (left, right) => {
        // 已经到底了
        if(left > right){
            return [null]
        }
        if(left === right){
            return [new TreeNode(left)];
        }
        let res = [];
        for (let i = left; i <= right ; i++) {
            // i 是当前作为 根 的index， 下面进行分治
            let leftTrees = dfs(left, i - 1);
            let rightTrees = dfs(i + 1,right);
            // 下面要所有种类，其实就是集合的笛卡尔乘积
            for (let leftTree of leftTrees) {
                for (let rightTree of rightTrees) {
                    let root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    res.push(root);
                }
            }
        }
        return res;
    }
    return dfs(1,n);
}

// 通过缓存的方式来记录结果
const generateTrees2 = (n) => {
    if (n === 0) return [];
    const memo = new Array(n + 1);
    for (let i = 0; i < memo.length; i++) {
        memo[i] = new Array(n + 1);
    }
    const getAllBSTs = (low, high) => {
        if (low > high) return [null];
        if (memo[low][high]) return memo[low][high];
        if (low === high) return [new TreeNode(low)];
        const res = [];
        for (let i = low; i <= high; i++) {
            const leftBSTs = getAllBSTs(low, i - 1);
            const rightBSTs = getAllBSTs(i + 1, high);
            for (const leftBST of leftBSTs) {
                for (const rightBST of rightBSTs) {
                    const root = new TreeNode(i);
                    root.left = leftBST;
                    root.right = rightBST;
                    res.push(root);
                }
            }
        }
        return memo[low][high] = res;
    };
    return getAllBSTs(1, n);
};

/**
 * 文斌大大龙算法第 【41】 篇
 * LeetCode 算法第 98 题目
 *
 * 验证 二叉搜索树 BST
 *
 * 二叉搜索树有如下特征
 * 1. 节点的左子树只包含小于当前节点的数
 * 2. 节点的右子树只包含大于当前节点的数
 * 3. 所有的左子树和右子树自身也必须是二叉搜索树
 */

const isValidBST = function(root){
    const dfs = (root, minVal, maxVal) => {
        if(root === null) return true;
        if(root <= minVal && root >= maxVal) return false;
        return dfs(root.left, minVal, root.value) && dfs(root.right, root.value, maxVal);
    }
    return dfs(root, -Infinity, Infinity);
}

/**
 * 文斌大大龙算法第 【41】 篇
 * LeetCode 第 96 题
 *
 * 不同的搜索二叉树 BST
 *
 * 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
 *
 * BST + 动态规划
 */

const numsBST = function(n){
    if(n === 0) return 1;
    if(n === 1) return 1;
    let num = 0;
    for (let j = 0; j < n; j++) {
        num += numsBST(j) * numsBST(n-j-1);
    }
    return num;
}

// 我们也可以将计算结果存起来
const numsBSTHasCache = function(n){
    const cache = new Map();
    const divideAndConquer = (n) => {
        if(n ===0 || n === 1) return 1;
        if(cache.has(n)) return cache.get(n);
        let num = 0;
        for(let j = 0; j < n; j++){
            num+= divideAndConquer(j) * divideAndConquer(n -j -1);
        }
        // 缓存本次结果，提供给下次使用
        cache.set(n,num);
        return num;
    }
};

/**
 * 文斌大大龙 第 42 篇
 *
 * LeetCode 第 100 题
 *
 * 相同的树 (二叉树)
 *
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 */

const isSameTree = function(p,q){
    if(p=== null && q === null) return true;
    if(p !== null && q !== null){
        if(p.value !== q.value){
            return false;
        }else{
            return isSameTree(p.left, q.left) && isSameTree(p.right,q.right);
        }
    }else{
        return false;
    }
}

/**
 * 文斌大大龙 第【42】篇
 * LeetCode 101 题目
 * 对称对称二叉树
 *
 * 给定一个二叉树，检查它是否是镜像对称的。
 */

const isSymmetryTree = function(root){
    const isMirror = function(tree1, tree2){
        if(tree1 === null && tree2 === null){
            return true;
        }
        if(tree1 === null || tree2 === null){
            return false;
        }
        return tree1.value === tree2.value &&
            isSymmetryTree(tree1.left, tree2.right) &&
            isSymmetryTree(tree1.right, tree2.left);
    }
    return isMirror(root,root);
}

/**
 * 文斌大大龙算法第【43】篇
 * LeetCode 第 102 题目
 *
 * 二叉树的层序遍历
 *
 */

const levelOrderTraverse = function(root){
    let res = [];
    let queue = [];
    queue.push(root);
    while (queue.length){
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            res.push(node.value);
            if(node.left){
                queue.push(node.left)
            }
            if(node.right){
                queue.push(node.right);
            }
        }
    }
    return res;
};

/**
 * 文斌大大龙算法第【44】篇
 * LeetCode 第 104 题目
 *
 * 二叉树最大深度
 * 解题方法 程序遍历
 */

const binaryTreeMaxDepth = function(root){
    if(root === null) return 0;
    let level = 0;
    let queue = [];
    queue.push(root);
    while (queue.length){
        let size = queue.length;
        for (let i = 0; i < size; i++) {
            let node = queue.shift();
            if(node.left){
                queue.push(node.left)
            }
            if(node.right){
                queue.push(node.right)
            }
        }
        level += 1;
    }
    return level;
};

/**
 * 文斌大大龙算法 【44】 篇
 *
 * 二叉树 利用前序遍历 和 中序遍历构造一个二叉树
 *
 * 算法就是分治法 通过递归都方式来处理
 */

const buildTreeByPreAndMid = function(preOrder, inOrder){
    if(preOrder.length === 0){
        return null;
    }
    // 根据前序数组的第一个元素， 就可以确定根节点
    let root = new TreeNode(preOrder[0]);
    // 定位根节点在中序遍历的位置
    let midIndex = inOrder.indexOf(root.value);
    // 那么左边就是左子树节点个数，右子树节点个数都知道了。
    root.left = buildTreeByPreAndMid(preOrder.slice(1, midIndex + 1), inOrder.slice(0, midIndex));
    root.right = buildTreeByPreAndMid(preOrder.slice(midIndex + 1),inOrder.slice(midIndex + 1));
    return root;
};
/**
 * 文斌大大龙算法 【44】篇
 * 二叉树 中序遍历 和 后序遍历构二叉树
 */
const buildTreeByMidAndPost = function(inOrder, postOrder){
    if(inOrder.length === 0) return null;
    // 后序遍历最后欧一个节点是根节点
    let root = new TreeNode(postOrder(postOrder.length - 1));
    // 找到根节点，这样可以计算出左、右子树各有多少个节点
    let minIndex = inOrder.indexOf(root.value);
    root.left = buildTreeByMidAndPost(inOrder.slice(0,minIndex), postOrder.slice(0,minIndex));
    root.right = buildTreeByMidAndPost(inOrder.slice(minIndex + 1), postOrder.slice(minIndex, postOrder.length - 1));
    return root;
};

/**
 * 文斌大大龙 【44】篇
 *
 * 二叉树前序遍历和后序遍历构造二叉树
 */

const buildTreeFromPrePost = function(preOrder, postOrder){
    if(preOrder.length === 0) return null;
    let root = new TreeNode(preOrder[0]);
    // 优化递归出口， 前序序列长度为1，这表示它没有左子了，可以直接返回
    if(preOrder.length === 1){
        return root;
    }
    let left_list_len = postOrder.indexOf(root.value);
    root.left = buildTreeFromPrePost(preOrder.slice(1,left_list_len + 1), postOrder.slice(0,left_list_len));
    root.right = buildTreeFromPrePost(preOrder.slice(left_list_len + 1), postOrder.slice(left_list_len, postOrder.length - 1));
    return root;
};

/**
 * 文斌大大龙第 45 篇
 *
 * 将有序数组转换成为二叉搜索树
 *
 * 二叉搜索树左子树上所有节点值均小于它的根节点的值， 右子树上所有节点的值均大于它的根节点的值
 * 二叉搜索树的中序遍历结果为递增序列
 */

const sortedArrayToBST = function(nums){
    const buildBST = (nums, start, end) => {
        if(start > end) return null;
        let mid = start + Math.floor((end - start) / 2);
        const root = new TreeNode(nums[mid]);
        root.left = buildBST(nums, start, mid - 1);
        root.right = buildBST(nums, mid + 1, end);
        return root;
    }
    return buildBST(nums, 0, nums.length - 1);
};


/**
 * 文斌大大龙算法第【46】篇
 * LeetCode第 110 题
 * 判断平衡二叉树
 *
 * 解法思路 递归法
 *
 * 1. 我们实现一个求二叉树深度的函数
 *    当节点为空时返回 0;
 *    要不选其左右子树更深的一条路深度 + 1
 * 2. 递归的判断是否是平衡二叉树
 *    root === null 是递归的出口
 *    左右子树深度差小于 1
 *    递归判断左右子树是否平衡即可
 */
const depth = function(root){
    if(root === null) return 0;
    return Math.max(depth(root.left), depth(root.right)) + 1;
}
const isBalanceTree = function(root){
    if(root === null){
        return true;
    }
    return Math.abs(depth(root.left) - depth(root.right)) <= 1 &&
        isBalanceTree(root.left) && isBalanceTree(root.right)
};

/**
 * 文斌大大龙算法第【48】 篇
 * LeetCode第 120 题
 *
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。
 * 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 * 解法思路 动态规划发 DP 算法
 *
 */

const minimumTotal = function(triangle) {
    if(triangle.length === 1) return triangle[0][0];
    // 这地方为什么是 i = triangle.length - 2;
    // 因为是从倒数第二行开始遍历，否则下面的triangle[i+1]就溢出了
    for (let i = triangle.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; i++){
            triangle[i][j] = Math.min(
                triangle[i+1][j] + triangle[i][j],
                triangle[i+1][j+1] + triangle[i][j]
            );
        }
    }
    return triangle[0][0];
};

/**
 * 文斌大大龙算法 第 【49】 篇
 * 二叉树最近公共祖先节点
 *
 * 算法思路是递归寻找 包含 P 与 Q 节点的树
 *
 * 递归算法 首先设置边界条件 直到该再什么地方跳出循环
 */
const lowestCommonAncestor = function(root,p,q){
    if(!root || root === p || root === q){
        return root;
    }
    let leftTree = lowestCommonAncestor(root.left,p,q);
    let rightTree = lowestCommonAncestor(root.right,p,q);
    if(leftTree && rightTree){
        return root;
    }else{
        return leftTree ? leftTree : rightTree;
    }
};

/**
 *  文斌大大龙算法 【50】 篇
 *  LeetCode 第 51 题
 *  N 皇后问题
 *  解题思路 DFS + 回溯
 */

const solveNQueues = function(n) {
    let res = [];
    const board = new Array(n).fill(0).map(item => new Array(n).fill('.'));
    // 判断是否是合法位置函数，保证皇后之间不冲突
    const isValidPosition = (row, col) => {
        // 之前的每一行都要进行扫描
        for (let i = 0; i < row; i++) {
            for (let j = 0; j < col; j++) {
                // 如果该位置有Q，且同列或在同对角线上，则不合法
                // 同行这里不做判断，是因为我们就是按照一行一行来做的，所以不会同行
                if(
                    board[i][j] === 'Q'
                    && (j === col || i + j === row + col || i - j === row - col)
                ){
                    return false;
                }
            }
        }
        return true
    }
    const dfs = (row) => {
        if(row === n){
            // 已经是递归出口了 已经超过最后一行，保存当前的值
            let boardBackup = board.slice()
            let tempRes = boardBackup.map(item => item.join(""));
            res.push(tempRes);
            return;
        }
        // 开始遍历这一行每一行的位置
        for (let col = 0; col < n; col++) {
            if(isValidPosition(row, col)){
                board[row][col] = "Q";
                //递归的向下回溯
                dfs(row  + 1);
                // 回溯路径
                board[row][col] = ".";
            }
        }
    }
};

/**
 * 文斌大大龙算法第 【51】 篇
 * LeetCode 第 121 题目
 *
 * 买卖股票 I
 *
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 *
 * 本体的就是找到后面的最大值减去前面的最小值 这个就是解题思路
 *
 */

const maxProfit = function(prices){
    let [min_point, max_profit] = [Infinity,0];
    prices.map(item => {
        if(item < min_point){
            min_point = item;
        }else{
            max_profit = Math.max(item - min_point, max_profit);
        }
    })
    return max_profit
}

/**
 * 文斌大大龙算法第 【51】 篇
 * LeetCode 第 121 题目
 *
 * 买卖股票 II
 *
 * 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 *
 * 这个题目看似情况增多了，实际上更简单， 每次涨了就卖（不涨不卖），最大和就是每次涨了的钱的总和
 *
 */

const maxProfit2 = function(prices){
    let maxProfit = 0;
    for (let i = 0; i < nums.length - 1; i++) {
        if(prices[i] < prices[i + 1]){
            maxProfit += prices[i + 1] - prices[i];
        }else{
            continue
        }
    }
    return maxProfit;
}

const maxProfit2ByDP = function(prices){
    const dp = new Array(prices.length).fill([0,0]);
    dp[0][0] = -prices[0];
    for (let i = 1; i < prices.length; i++) {
        let price =prices[i];
        dp[i][0] = Math.max(dp[i-1][1] - price, dp[i-1][0]);
        dp[i][1] = Math.max(dp[i-1][0] + price, dp[i-1][1]);
    }
    return dp[prices.length - 1][1];
}

/**
 * 文斌大大龙算法 第 【51】 篇
 * LeetCode 第 123 题
 * 买卖股票的最佳时期
 * 方法一：动态规划
 * 思路与算法
 *
 * 由于我们最多可以完成两笔交易，因此在任意一天结束之后，我们会处于以下五个状态中的一种：
 *
 * 未进行过任何操作；
 *
 * 只进行过一次买操作；
 *
 * 进行了一次买操作和一次卖操作，即完成了一笔交易；
 *
 * 在完成了一笔交易的前提下，进行了第二次买操作；
 *
 * 完成了全部两笔交易。
 *
 * 由于第一个状态的利润显然为 0，因此我们可以不用将其记录。对于剩下的四个状态，我们分别将它们的最大利润记为
 * buy1, sell1,buy2,sell2
 *
 * 动态规划的关键是找出最优子结构， 找出状态转移方程
 *
 */

const maxProfit3ByDP = function(prices){
    const n = prices.length;
    let buy1 =- prices[0], buy2 =- prices[0];
    let sell1 = 0, sell2 = 0;
    for (let i = 1; i < n; i++) {
        buy1 = Math.max(buy1, -prices[i]);
        sell1 = Math.max(sell1,buy1 + prices[i]);
        buy2 = Math.max(buy2, sell1 - prices[i]);
        sell2 = Math.max(sell2, buy2 + prices[i]);
    }
    return sell2;
}

/**
 * 买卖股票 含冷冻期
 * 含有冷冻期的，因此在任意一天结束之后， 我们会处于以下3个状态中的一种
 * 手中没持有，可以买
 * 手中持有，可以卖
 * 冷冻期，手中没持有，买不了
 */

const maxProfit3 = function(prices){
    let [buy, sell, sellPre] = [-Infinity, 0, 0];
    for (let i = 0; i < prices.length; i++) {
        buy = Math.max(buy, sellPre - prices[i]);
        sellPre = sell;
        sell = Math.max(sell, buy + prices[i]);
    }
}

/**
 * 文斌大大龙算法第 【53】 篇
 * LeetCode 206 题
 * 反转链表
 *  给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
 */

const reverseList = function(head){
    let [pre, cur] = [null, head];
    while (cur){
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
}

/**
 * 文斌大大龙算法 【53】 篇
 * LeetCode第 141 题
 *
 * 环形链表
 *
 * 给定一个链表的头节点， 判断链表中是否有环
 *
 */

const hasCycle = function(head){
    let [slow, fast] = [head, head];
    while (slow && fast &&fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow) return true;
    }
    return false;
};

/**
 * 文斌大大龙算法第 【54】篇
 * LeetCode 第 142 题
 * 环形链表 II
 *
 * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 */

const detectCycle = function(head){
    let [slow, fast] = [head, head];
    while(slow && fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow === fast){
            slow = head;
            while(slow !== fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

/**
 * 文斌大大龙算法 【54】 篇
 * LeetCode 第 25 题
 * K 个一组翻转链表
 *
 */

const reserveByKGroup = function(head, k){
    let [pre, cur, p] = [null, head, head];
    for (let i = 0; i < k; i++) {
        if(p === null) return head;
        p = p.next;
    }
    for (let i = 0; i < k; i++) {
        let next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    head.next = reserveByKGroup(cur, k);
    return pre;
};


/**
 * 文斌大大龙算法第【56】题
 * LeetCode 第 703 题
 * 队列中数据流中第 K 大的元素
 *
 * 算法实现 实现一个优先队列
 */

const defaultCmp = (x, y) => x > y;
const swap = (arr, i, j) => ([arr[i],arr[j]] = [arr[j],arr[i]]);

class Heap {
    /**
     * 默认是最大堆
     * @param {Function} cmp
     */
    constructor(cmp = defaultCmp) {
        this.container = [];
        this.cmp = cmp;
    }
    // 插入元素

    insert(data){
        const {container, cmp} = this;
        container.push(data);
        let index = container.length - 1;
        while (index){
            let parent = Math.floor((index - 1) / 2);
            if(!cmp(container[index], container[parent])){
                return;
            }
            swap(container, index, parent);
            index = parent;
        }
    }
    // 弹出堆顶元素
    extract(){
        const { container, cmp } = this;
        if(!container.length){
            return null;
        }
        swap(container, 0, container.length - 1);
        const res = container.pop();
        const length = container.length;
        let index = 0, exchange = index * 2 + 1;
        while(exchange < length){
            let right = index * 2 + 2;
            if(right < length && cmp(container[right],container[exchange])){
                exchange = right;
            }
            if(!cmp(container[exchange],container[index])){
                break;
            }
            swap(container, exchange, index);
            index = exchange;
            exchange = index * 2 + 1;
        }
        return res;
    }
    // 获取堆顶元素
    top(){
        if(this.container.length) return this.container[0];
        return null;
    }
};

